1. Field of the Invention
The invention described herein is related to determining an amount of noncompliant communication network traffic for purposes of detecting a distributed denial of service (DDoS) attack. More specifically, the present invention actively drops certain packets from an aggregate of traffic flows in a communication network and then measures the data traffic rate subsequent thereto. In so doing, the present invention can determine an amount of traffic not conforming to the transmission protocol of the aggregate, which is an indication of a DDoS attack.
2. Description of the Prior Art
A distributed denial of service (DDoS) attack is a communication disruption technique for hindering applications used, generally, to conduct electronic commerce over the Internet. Current operational speeds of network equipment allow participants in a DDoS attack to inject into the Internet a tremendous amount of pernicious traffic over a very short time interval in so called “traffic storms” to intentionally cause disruptions in Internet communications.
A traffic flow is defined as a stream of data packets emanating from the same source and bound for the same destination and which are transported along the same path. In Applicants' previously-filed U.S. patent application Ser. No. 10/825,111, the conformance of an aggregate of traffic flows to a communication protocol, e.g., the Transmission Control Protocol (TCP), was measured by perturbing the rate of traffic belonging to that aggregate, e.g., by intentionally dropping a small number of packets, and observing how the traffic rate of the aggregate responds. A compliant TCP aggregate is predictable in its response to instantaneous packet drops and that predictability is exploited to measure conformance of the aggregate to the protocol. This method is referred to as the Aggregate Perturbation Method (APM).
One complication of APM is that, in a distributed implementation, interference may result from simultaneous tests being performed at different routers. That is to say, flows in an aggregate may experience perturbations by tests executed at each of multiple routers leading to erroneous measurements. To be effective in such a distributed application, a router should measure the response to its own perturbation and such measurement should not be influenced by the perturbations applied at other routers. As described in the above-cited U.S. patent application Ser. No. 10/825,111, a solution to this problem is inspired by the direct-sequence spread-spectrum code division multiple access (CDMA) approach in multiple access communication channels. According to the technique, each router is assigned a packet dropping signature to specify a corresponding packet dropping rate as a function of time. Each participating router is assigned a signature that is orthogonal in some sense to the signature of other such routers. Under certain assumptions, this approach enables each individual router to measure conformance to the transmission protocol of aggregates passing through it without requiring any information to be shared with the other routers. This technique is referred to as the CDMA-based Aggregate Perturbation Method (CAPM).
A technical limitation of CAPM, as described in U.S. patent application Ser. No. 10/825,111, lies in the fact that a nominal traffic response to dropped packets depends on such traffic characteristics as the average lifetime of the flows forming the aggregate, the round trip times of transmitted packets, and the statistical distribution of the congestion control window size. Thus, when a single packet is dropped from an aggregate, the corresponding rate reduction is only known if long-term statistical measurements of the aggregate are available. Such limitation is prohibitive in DDoS applications, where rapid detection and response is desired.
Several techniques for mitigating DDoS attacks are known in the art, including pushback, traceback, and ingress filtering. Pushback includes detection of an attack, identification of the attack signature, and notification to an upstream traffic filter to limit the rate of the attack traffic. Traceback techniques are designed to follow the offending traffic's path to, ultimately, the source of the attack. In certain prior art systems, routers store hashed information on recently received packets to recover the paths to the packet source in the event that traceback is needed.
In ingress filtering, edge routers check the validity of the source Internet Protocol (IP) addresses of the packets. A packet with a source IP address that does not belong to any of the valid sources in the network is filtered by the edge router of that network. In another technique, the traffic at an egress router of a stub domain is monitored to determine whether the ratio of outgoing to incoming traffic for a set of remote addresses is abnormally high. A high ratio is taken as a signal that an attack is being mounted from within the stub domain.
Research has been conducted to identify and model Transmission Control Protocol (TCP) traffic in flows under steady state conditions. For example, the steady state throughput of a TCP flow may be compared with a theoretically predicted value to identify conforming flows. This technique has been used in the past to identify and penalize nonconforming flows for congestion control purposes. One such technique, referred to as Stochastic Fair Blue, performs a per-flow test for responsiveness by mapping different flows to parallel bins relying on the fact that the bins containing a nonconforming flow are likely to be overloaded. However, if many nonconforming flows exist, it is likely that many bins are overloaded and the procedure will not be able to distinguish between conforming and non-conforming flows.
Given the state of the prior art, the need is apparent for a technique to rapidly identify the onset of a DDoS attack without the requirement of long-term compilations of historical data and without the need to share information among participating routers to identify the attack.